// //
// class Solution {
//     vector<vector<string>> ret;
//     vector<string> path;
//     int is_existent[9][9] ={0} ; //0代表下标列未被选择，1代表下标列已经被选择
//     int _n;
//     bool is_ok(int line,int row){
//         for(int i = 0 ; i < line ; i++){
//             if(is_existent[i][row] == 1)  return false;
//             for(int j = 0; j < _n ; j++){
//                 if(is_existent[i][j] == 1){
//                     if(abs(line-i) == abs(row-j)) return false;
//                 }
//             }
//         }
//         return true;
//     }
// public:
//     vector<vector<string>> solveNQueens(int n) {
//         _n = n;
//         dfs(0);
//         return ret;
//     }
//     void dfs(int story ){
//         if(story == _n){
//             ret.push_back(path);
//             return;
//         }
//         for(int i = 0; i < _n ; i++){
//             if(is_ok(story,i)){
//                 string s(_n,'.');
//                 s[i] = 'Q';
//                 path.push_back(s);
//                 is_existent[story][i]=1;
//                 dfs(story+1);
//                 is_existent[story][i]=0;//恢复现场
//                 path.pop_back();
//             }
//         }
//     }
// };
class Solution {
    vector<vector<string>> ret;
    vector<string> path;
    int checkcol[9],checkdig1[18],checkdig2[18];
    int _n;
public:
    vector<vector<string>> solveNQueens(int n) {
        _n = n;
        dfs(0);
        return ret;
    }
    void dfs(int story ){
        if(story == _n){
            ret.push_back(path);
            return;
        }
        for(int i = 0; i < _n ; i++){
            if(checkcol[i] == 0 && checkdig1[story-i+9] == 0 && checkdig2[story+i] == 0){
                string s(_n,'.');
                s[i] = 'Q';
                path.push_back(s);
                checkcol[i] = 1; checkdig1[story-i+9] = 1;checkdig2[story+i] = 1;
                dfs(story+1);
                checkcol[i] = 0; checkdig1[story-i+9] = 0;checkdig2[story+i] = 0;//恢复现场
                path.pop_back();
            }
        }
    }
};
